import javax.swing.tree.TreeNode;
import java.util.*;

//之字型层序遍历
public class Test {
    //法一
//    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
//        Queue<TreeNode> queue = new LinkedList<>();
//        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
//        Stack<TreeNode> stack = new Stack<>();
//        Queue<TreeNode> queue1 = new LinkedList<>();
//        ArrayList<Integer> list3 = new ArrayList<>();
//        list3.add(pRoot.val);
//        list.add(list3);
//        int i=1;
//
//        queue.offer(pRoot);
//        while(!queue.isEmpty()){
//            int size=queue.size();
//            TreeNode cur=null;
//            ArrayList<Integer> list2 = new ArrayList<>();
//
//
//            if(i%2==1){
//                while(size!=0){
//                    cur=queue.poll();
//
//                    if(cur.left!=null){
//                        queue.offer(cur.left);
//                        stack.push(cur.left);
//                    }
//                    if(cur.right!=null) {
//                        queue.offer(cur.right);
//                        stack.push(cur.right);
//                    }
//                    size--;
//                }
//                while(!stack.isEmpty()){
//
//                    list2.add(stack.pop().val);
//                }
//                i++;
//                if(list2!=null)
//                list.add(list2);
//            }else{
//                while(size!=0){
//                    cur=queue.poll();
//                    if(cur.left!=null){
//                        queue.offer(cur.left);
//                        list2.add(cur.left.val);
//                    }
//                    if(cur.right!=null) {
//                        queue.offer(cur.right);
//                        list2.add(cur.right.val);
//                    }
//                    size--;
//                }
//                i++;
//                list.add(list2);
//            }
//        }
//        return list;
//    }
               //法二：
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(pRoot==null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        Boolean tmp = false;
        queue.offer(pRoot);
        while(!queue.isEmpty()){
            ArrayList<Integer> list2 = new ArrayList<>();
            int size = queue.size();
            while(size!=0){
                TreeNode cur = queue.poll();
                list2.add(cur.val);
                if (cur.left!=null){
                    queue.offer(cur.left);
                }
                if (cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
            if (tmp==false){
                tmp=true;
            }else{
                Collections.reverse(list2);
                tmp=false;
            }
            list.add(list2);
        }
        return list;
    }


}
